支持向量机 Support Vector Machines

支持向量机(SVM)是一种非常强大且通用的机器学习模型，其能够执行线性或非线性分类、回归，甚至是异常值检测等任务。它是机器学习中最流行的模型之一，任何对机器学习感兴趣的人都应该把它放在自己的工具箱里。支持向量机特别适合于对中小型复杂数据集进行分类。本章将解释支持向量机的核心概念，以及如何使用它们和它们是如何工作的。

Linear SVM Classification（线性支持向量机分类）

本书将会使用一些图片来解释支持向量机背后的基本思想。图5-1显示了第4章末尾介绍的鸢尾花数据集的一部分内容。可以看到，图中的两个类别可以很容易地用直线分开(它们是线性可分离的)。

左边的图显示了线性分类器决策边界的三种可能。其中虚线所表示的决策边界的模型非常糟糕，其甚至不能正确的进行分类。而另外两个模型在这个训练集上工作得很好，但是它们的决策边界非常接近实例，这可能会影响模型的泛化性能。与之相对的，图中右侧实线表示SVM分类器的决策边界;这条线不仅很好地分隔了两个类，而且还尽可能地远离最近的训练实例，这是相当优秀的决策边界。

你可以将SVM分类器看作是在类之间拟合最宽的间隔(由右图中的平行虚线表示)，我们称其为最大间隔分类。

请注意，添加更多“远离间隔”的训练实例根本不会影响决策边界:决策边界完全由位于间隔边缘的实例确定(或“支持”)。这些实例称为支持向量(图5-1中被圈起来的实例)。

支持向量机对特征尺寸很敏感，如图所示:在左图中，垂直尺度远大于水平尺度，所以最宽的间隔接近水平。在进行特征缩放（例如，使用Scikit-Learn的StandardScaler）之后，决策边界看起来就好很多。

软间隔分类

如果我们严格要求所有的实例都不在间隔内，而处于间隔两侧，则称之为硬间隔分类。

硬间隔分类主要有两个问题：首先，它只在数据是线性可分的情况下有效；其次，它对异常值非常敏感。

图5-3显示了鸢尾花数据集，只有一个额外的异常值:在左图,找不到一个合适的硬间隔；在右图中，决策边界与我们在图5-1中看到的没有异常值的情况完全不同，并且该分类器在新数据上的泛化性能不会很好。

为了避免这些问题，最好使用更灵活的模型。目标是在保持间隔尽可能大与限制错误分类之间找到一个良好的平衡。例如分类后的实例可能会出现在间隔中间甚至是错误的分类一侧，这就是所谓的软间隔分类。

在Scikit-Learn的SVM类中，你可以使用C超参数控制这种平衡:较小的C值会导致更宽的间隔，但会有更多的错误分类。图5-4显示了两个软间隔SVM分类器在非线性可分数据集上的决策边界和间隔。在左图中，使用一个较低的C值，间隔会相当大，但很多实例会出现在间隔中。在右侧，使用较高的C值，分类器的错误分类很少，但最终得到的间隔更小。

看起来第一个分类器有更好的泛化性能，因为大多数间隔违例都处于决策边界正确的一边，所以即使是在该训练集上，它所做出的错误预测也更少。

如果你的支持向量机模型过拟合了，可以尝试调低超参数Ｃ。

下面的Scikit-Learn代码加载鸢尾花数据集，进行缩放特征，然后训练一个线性SVM模型(使用C = 1的LinearSVC类和合页(hinnge)损失函数，稍后会介绍)来检测Iris-Virginica花。最终的结果显示在5-4的右侧。

用以上训练好的模型进行预测

下面的代码对不同正则化参数进行比较。

与logistic回归分类器不同，SVM分类器不输出每个类的概率。当然，你也可以有更多选择：

LinearSVC类会正则化偏置(bias),所以在使用时应该先首先通过减去其平均值来使训练集居中。如果使用StandardScaler缩放数据，则会自动执行此操作。此外，请确保将损失超参数设置为“hinge”，因为它不是默认值。最后，为了获得更好的性能，您应该将双超参数设置为False，除非特征数比训练实例多（我们将在本章后面讨论二元性）。

非线性支持向量机分类

尽管线性SVM分类器在多数情况下是有效的，并且有着非常好的效果，但许多数据集不是线性可分的。处理非线性数据集的一种方法是添加更多的特征，如多项式特征(见第四章);在某些情况下，这样操作会使数据集线性可分。

考虑图5-5中左边的图:它表示只有一个特征x1的简单数据集。这个数据集不是线性可分的。但是如果你加入一个二次特征$x_2 =(x_1)^2$，得到的2D数据集是完全线性可分的。

图5-5

要使用Scikit-Learn实现这个想法，你可以创建包含PolynomialFeatures变换器的程序（在第121页的“多项式回归”中讨论的），然后是StandardScaler和LinearSVC。 让我们在moons dataset 上测试一下（见图5-6）：

图5-6

多项式核函数

添加多项式特征这一操作实现起来比较简单,可以用于各种各样的机器学习算法(不仅仅是支持向量机),但在低阶多项式不能处理非常复杂的数据集；而高阶多项式会产生大量的特征，拖累模型的速度。

幸运的是，在使用支持向量机时，你可以使用一种奇迹般的数学技巧，我们称之为核技巧(稍后将对此进行解释)。核技巧可以获得与添加许多多项式特征相同的结果，即是该结果需要添加非常高阶的多项式，使用核技巧也能获得同样的结果。因此，由于我们实际上并没有添加任何特征，因此就可以避免特征之间的组合爆炸。该技巧由SVC类实现。我们可以在moons数据集上去测试它的性能。

上面的代码使用３阶多项式内核训练SVM分类器。而右图是使用10阶多项式内核的SVM分类器。显然，如果模型过拟合，你可能希望降低多项式次数。如果模型欠拟合，你可以尝试增加多项式次数。

超参数coef0控制模型受高阶多项式与低阶多项式的影响程度。

找到正确超参数值的一种常用方法是使用网格搜索(见第2章)。首先做一个非常粗糙的网格搜索，然后根据找到的最佳值进行更精细的网格搜索，这种做法通常会获得更快的速度。

充分了解每个超参数的实际作用可以更有效的在超参数空间中进行搜索。

添加相似特征

解决非线性问题的另一种技术就是添加相似特征。这些特征可以通过计算相似函数得出，相似函数可以测量每个实例与一个特定地标之间的相似度。以前面提到的一维数据集为例，在 $x_1 = -2$ 和 $x_1 = 1$ 处为其添加两个标签。然后使用高斯径向基函数(RBF)作为相似函数，y=0.3。

$\phi_{\gamma}(\mathbf{x}, \ell)=\exp \left(-\gamma\ || \mathbf{x}-\ell\ || ^{2}\right)$ 它是一个钟形函数，从0（距地标很远）到1（在地标处）不等。现在我们已准备好计算新特征。例如，让我们看一下实例$x_1 = -1$ ：它位于距第一个地标距离为1的地方，距第二个地标距离为 2。因此，其新特征是 $x_2 = exp（-0.3×1^2）≈0.74$ 并且 $x_3 = exp（-0.3×2^2）≈0.30$。 右侧的图显示了转换后的数据集（删除原始特征）。如您所见，它现在可以线性分离了。

那我们如何选择地标呢？最简单的方法是在数据集中每个实例的位置创建一个地标。这样就创建了许多维度，从而就增加了训练集可分离的可能性。缺点就是具有m个实例和n个特征的训练集被转换成就有m个实例和m个特征的训练集（假设你删除了原始特征）。如果你的训练集十分庞大，那么就会获得同样大数量的特征。

高斯径向基核函数

与多项式特征方法一样，相似特征法也可以用于任何机器学习算法，但计算所有的附加特征可能导致很高的计算成本，特别是在大型数据集上。然而，核技巧再一次施展了SVM魔术：它可以在不添加许多相似特征的前提下达到添加相似特征的性能。让我们来使用SVC类来尝试一下高斯径向基核：

图5-9的左下方显示了这个模型。其他图显示了使用不同超参数值gammay()和C训练的模型。增加gamma值会使钟形曲线变窄(如5-8左图所示)，因此每个实例的影响范围都随之变小：决策边界变得更不规则，开始围着单个实例绕弯。反过来，减小gamma值使得钟型函数变得更宽，因此实例就具有更大的影响范围，决策边界也就变得更加平滑。 所以γ就像一个正则化超参数：如果你的模型过拟合，你应该减少它，如果它是欠拟合，你应该增加它（类似于C超参数）。

除了我们上面提到的多项式内核和高斯RBF内核，还存在其他内核但很少使用。例如，某些内核专门用于特定的数据结构。 在分类文本文档或DNA序列时，有时会使用字符串内核（例如，使用字符串子序列内核或基于Levenshtein距离的内核）。

在实际应用中我们有多种内核可以去选择，我们如何决定使用哪一个？ 你应该首先尝试线性内核（请记住，LinearSVC比SVC(内核=“线性”)快得多），特别是如果训练集非常大或者它有很多特征。 如果训练集不是太大，你应该试试高斯RBF内核也是如此; 它在大多数情况下效果很好。 然后，如果你有空闲时间和计算能力，您还可以使用交叉验证和网格搜索来尝试其他一些内核，特别是如果有专门针对您的训练集的数据结构的内核。

计算复杂性

LinearSVC类基于liblinear库，其为线性SVM实现了一个优化算法。该算法不支持核技巧，不过它与训练实例的数量和特征数量几乎呈线性相关:其训练时间复杂度大致为O(m×n)。

如果你想得到非常高的精度，该算法需要更长的时间。这由容差超参数$ε$（在Scikit-Learn中称为tol）控制。在大多数分类任务中，默认容差就够了。

SVC类基于libsvm库，该库实现了支持内核技巧的算法。训练时间复杂度通常在$ O（m_2×n）$和 $O（m_3×n）$之间。不幸的是，这意味着当训练实例的数量变大（例如，数十万个实例）时，它变得非常慢。该算法适用于复杂但小型或中型训练集。但是，它随着特征的数量很好地扩展，特别是对于稀疏特征（即，当每个实例具有很多的零特征时）。在这种情况下，算法大致按每个实例的非零特征的平均数量进行缩放。

表5-1比较了Scikit-Learn的SVM分类类。

表格5-1

image-20200731163825431

SVM回归

正如我们前面提到的一样，SVM算法十分通用：它不仅支持线性和非线性分类，还支持线性与非线性回归。其中的关键点是转换目标：SVM回归不是拟合两个分类之间的最宽间隔的同时限制间隔违例，其要做的是让尽可能多的实例位于间隔之间，同时限制间隔违例（不在间隔间的实例）。间隔的宽度由超参数$ε$控制。图5-10显示了在一些随机线性数据上训练的两个线性SVM回归模型，一个具有较大的宽度$（ε= 1.5）$，另一个具有较小的宽度$（ε= 0.5）$。

在间隔内添加更多训练实例不会影响模型预测; 因此，该模型被认为是$ε-不敏感( ϵ -insensitive.)$。

您可以使用Scikit-Learn的LinearSVR类来执行线性SVM回归。以下代码生成图5-10左侧所示的模型（训练数据应先缩放并居中）：

图5-10

要处理非线性回归任务，可以使用核化的SVM模型。例如，图5-11显示了在一个随机二次训练集上，使用二阶多项式核的SVM回归。左图几乎没有正则化（Ｃ值很大），右图则是过度正则化（Ｃ值很小）。

以下代码使用Scikit-Learn的SVR类（支持内核技巧）生成图5-11左侧所示的模型。 SVR类与SVC类回归等价，LinearSVR类也与LinearSVC类的回归等价。 LinearSVR类与训练集的大小成线性比例（就像LinearSVC类一样），而当训练集变大时SVR类变得太慢（就像SVC类一样）。SVM也可用于异常值检测; 有关详细信息，请参阅Scikit-Learn的文档。

图5-11

工作原理

本节从线性支持向量机分类器开始，解释支持向量机是如何进行预测的，以及它们的训练算法是如何工作的。如果你刚刚开始机器学习，你可以跳过它，直接去看本章末尾的练习，然后当你想更深入地理解支持向量机时再回来学习。

首先，关于符号： 在第4章中，我们使用了将所有模型参数放在一个向量 $θ$ 中的惯例，包括偏置项 $θ_0 $ 和输入特征权重 $θ_1$ 到 $ θ_n $，并向所有实例添加偏置输入 $ x_0 = 1 $。 在本章中，我们将使用不同的约定，在处理SVM时更方便（也更常见）：偏置项将被称为 $ b $，而特征权重向量将被称为 $w$。在输入特征向量中不会添加偏差特征。

决策函数与预测

线性SVM分类器模型通过简单地计算决策函数 $ w^T·x + b = w_1 x_1 + ... + w_nx_n + b $ 来预测新实例 $x$ 的类：如果结果为正，则预测类 $ŷ$ 为正 类(1)，否则是负类(0); 见公式5-2。

$\hat{y}=\left\{\begin{array}{l}0 \text { if } \mathbf{w}^{T} \mathbf{x}+b<0 \\ 1 \text { if } \mathbf{w}^{T} \mathbf{x}+b \geq 0\end{array}\right.$ 公式５－２

图5-12显示了与图5-4右侧模型相对应的决策函数：因为该数据集有两个特征（花瓣宽度和花瓣长度），所以它是一个二维平面。决策边界是决策函数等于0的点集：它是两个平面的交点，它是一条直线（由粗实线表示）。

图5-12

虚线表示决策函数等于1或-1的点:它们与决策边界平行且距离相等，从而形成了一个间隔。训练一个线性SVM分类器意味着找到w和b的值，使这个边界尽可能宽，同时避免边界违规(硬边界)或限制边界(软边界)

训练目标

让我们来思考一下决策函数的斜率，它等于权重向量的范数，即$ ||w|| $。如果我们将斜率除以２，那么决策函数等于±1的点将远离决策边界两倍。换句话说，将斜率除以2将使边距乘以2。也许这在图5-13(即下面代码所绘制的图)中的2D图中更容易可视化。 权重向量 w 越小，间隔越大。

权重越小，间隔越大

所以我们要最小化$ ||w|| $来得到尽可能大的间隔。但是，如果我们想避免任何间隔违例（硬间隔），那么就要使所有正类训练集的决策函数大于１，负类训练集的决策函数小于-1, 如果我们为负实例定义 $t^{(i)}= -1$(如果$ y^(i)= 0$)并且对于正实例定义$t^{(i)}= 1$（如果$ y^(i)= 1$），那么对于所有实例我们可以将这个约束表达为$t^{(i)}(w ^T·x^{(i)}+ b)≥1$。因此，我们可以将硬间隔线性SVM分类器的目标表达为公式5-3中的约束优化问题：

\begin{aligned} &\operatorname{minimize}_{\mathbf{w}, b} \frac{1}{2} \mathbf{w}^{T} \mathbf{w}\\ &\text { subject to } \quad t^{(i)}\left(\mathbf{w}^{T} \mathbf{x}^{(i)}+b\right) \geq 1 \quad \text { for } i=1,2, \cdots, m \end{aligned}

式5-3

我们正在最小化$\frac{1}{2} w^T·w$，等价于 $\frac{1}{2}||w||^2$，而不是最小化$||w||$。这是因为它会给出相同的结果 （因为最小化一个值的 $w$ 和 $b$ 的值同时也最小化其平方的一半），但是$\frac{1}{2}||w||^2$有一个很好的简单的导数（它只是 $w$），而$||w||$在 $w = 0$ 时不可微分 优化算法在可微函数上运行得更好。

为了得软间隔分类的目标，我们需要为每个实例引入一个松弛变量$ζ^{(i)}≥ 0$：$ζ^{(i)}$ 测量允许第i个实例违反边界的程度。我们现在有两个相互矛盾的目标：使松弛变量尽可能小以减少边际违规（误分类），并使$\frac{1}{2} w^T·w$尽可能小以增加间隔。 这就是超参数C的用武之地：它允许我们定义这两个目标之间的权衡。这给出了我们公式5-4中的约束优化问题

\begin{aligned} &\underset{\mathbf{w}, b, \zeta}{\operatorname{minimize}} \quad \frac{1}{2} \mathbf{w}^{T} \mathbf{w}+C \sum_{i=1}^{m} \zeta^{(i)}\\ &\text { subject to } \quad t^{(i)}\left(\mathbf{w}^{T} \mathbf{x}^{(i)}+b\right) \geq 1-\zeta^{(i)} \text { and } \zeta^{(i)} \geq 0 \quad \text { for } i=1,2, \cdots, m \end{aligned}

式 5-4

二次规划

硬间隔和软间隔问题都是线性约束的凸二次优化问题。这些问题被称之为二次规划（QP）问题。要求解二次规划问题有很多现成的求解器，使用到的技术各不相同，这些不在本书的讨论范围之内。公式5-5给出了问题的一般形式。

$\begin{array}{ll}\text { Minimize } & \frac{1}{2} \mathbf{p}^{T} \mathbf{H} \mathbf{p}+\mathbf{f}^{T} \mathbf{p}\end{array}$ subject to $\quad$ Ap $\leq$ b Where $\left\{\begin{array}{ll}\mathbf{p} & \text { is an } n_{p} \text { -dimensional vector }\left(n_{p}=\right.\text { number of parameters) } \\ \mathbf{H} & \text { is an } n_{p} \times n_{p} \text { matrix, } \\ \mathbf{f} & \text { is an } n_{p} \text { -dimensional vector, } \\ \mathbf{A} & \text { is an } n_{c} \times n_{p} \text { matrix }\left(n_{c}=\right.\text { number of constraints) } \\ \mathbf{b} & \text { is an } n_{c} \text { -dimensional vector. }\end{array}\right.$ 公式5-5

注意，表达式$ A·p ≤ b$实际上定义了$n_c$个约束：对于$i = 1,2，⋯，n_c$，$p^T·a^{(i)}≤b^{(i)}$，其中$a^{(i)}$是包含$A$第 $i$ 行元素的向量, $b（i） $是 $b $的第 $i$ 个元素。

您可以轻松验证如果以下列方式设置QP参数，得到硬间隔线性SVM分类器目标：

所以，要训练硬间隔线性SVM分类器，其中一种方法是直接将上面的参数用在一个现成的二次规划求解器上。得到的向量$p$将包含偏置项$b = p_0$，并且对于$i = 1,2，...，m$，特征权重$w_i = p_i$。同样，您可以使用QP求解器来解决软间隔问题（参见本章末尾的练习）。

然而，为了使用核技巧，我们将研究一个不同的约束优化问题。

对偶问题

给定一个约束优化问题，称为原始问题，有可能表达一个不同但密切相关的问题，称其为对偶问题。对偶问题的解决方案通常给出原始问题的解决方案的下限，但在某些条件下它甚至可以具有与原始问题相同的解决方案。幸运的是，SVM问题碰巧满足这些条件，因此您可以选择解决原始问题或对偶问题;两者都有相同的解决方案。 公式5-6显示了线性SVM目标的对偶形式（如果您有兴趣知道如何从原始问题中导出对偶问题，请参阅附录C）。

$\operatorname{minimize}_{\alpha} \frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha^{(i)} \alpha^{(j)} t^{(i)} t^{(j)} \mathbf{x}^{(i)^{T} \mathbf{x}^{(j)}}-\sum_{i=1}^{m} \alpha^{(i)}$ subject to $\alpha^{(i)} \geq 0$ for $i=1,2, \cdots, m$ 公式５－６

一旦得到使该等式最小化（使用二次规划求解器）的向量$\hat{\alpha}$,就可以使用公式5-7来计算是原始问题最小化的$\hat{ w}$和$\hat{\ b}$

\begin{aligned} \widehat{\mathbf{w}} &=\sum_{i=1}^{m} \hat{\alpha}^{(i)} t^{(i)} \mathbf{x}^{(i)} \\ \hat{b}=\frac{1}{n_{s}} & \sum_{i=1}^{m}\left(t^{(i)}-\widehat{\mathbf{w}}^{T} \mathbf{x}^{(i)}\right) \end{aligned}

其中，第二个式子有条件为$\hat{\alpha}^{(i)}>0$
公式5-7

当训练实例的数量小于特征的数量时，对偶问题比原始问题解决得更快。更重要的是，它使核技巧成为可能，而原始问题不可以。那么这个核技巧究竟是什么呢？

核化SVM

假设你要将二维多项式变换应用于二维训练集（例如moons train set ），然后在变换的训练集上训练线性SVM分类器。公式5-8显示了要应用的第二个多项式映射函数:

$\phi(\mathbf{x})=\phi\left(\left(\begin{array}{c}x_{1} \\ x_{2}\end{array}\right)\right)=\left(\begin{array}{c}x_{1}^{2} \\ \sqrt{2} x_{1} x_{2} \\ x_{2}^{2}\end{array}\right)$ 公式5-8

注意，变换后的矢量是三维的而不是二维的。现在让我们来看看如果我们应用这个二次多项式映射，然后计算变换向量的点积（见公式5-9）。几个二维向量a和b会发生什么。 image-20200731163924185 公式5-9

变换矢量的点积等于原始矢量的点积的平方：$φ(a)^T·φ(b)=(a^T·b)^2$。

注意一下关键点：如果将变换$φ$应用于所有训练实例，那么对偶问题（见公式5-6）将包含点积$φ(x^{(i)})^T·φ(x^{(j)})$。但如果$φ$是公式5-8中定义的第二个多项式变换，然后你可以简单地用$(x^{{(i)}^T}·x^{(j)})^2$取代转换矢量的这个点积。所以你根本不需要转换训练实例： 只需用公式5-6中的平方替换点积。 结果将与您实际转换训练集然后拟合线性SVM算法的问题完全相同，但这个技巧使整个过程在计算上更有效率。 这是核技巧的本质。函数$K(a，b) =(a^T·b)^2$被称为二次多项式内核。在机器学习中，内核是能够仅基于原始矢量a和b计算点积$φ(a)^T·φ(b)$的函数，而不必计算（或甚至知道）变换$φ$。 公式5-10列出了一些最常用的内核：

$\begin{aligned} \text { Linear: } & K(\mathbf{a}, \mathbf{b})=\mathbf{a}^{T} \mathbf{b} \\ \text { Polynomial: } & K(\mathbf{a}, \mathbf{b})=\left(\gamma \mathbf{a}^{T} \mathbf{b}+r\right)^{d} \\ \text { Gaussian } \mathrm{RBF}: & K(\mathbf{a}, \mathbf{b})=\exp \left(-\gamma\|\mathbf{a}-\mathbf{b}\|^{2}\right) \\ \text { Sigmoid: } & K(\mathbf{a}, \mathbf{b})=\tanh \left(\gamma \mathbf{a}^{T} \mathbf{b}+r\right) \end{aligned}$ 公式5-10

Mercer定理

根据Mercer定理，如果函数$K（a，b）$符合几个数学条件————也就是Mercer条件（Ｋ必须是连续的，并且参数对称，所以$K（a，b）$＝$K（b, a）$）,则存在将a和b映射到另一个空间（可能具有更高维度）的函数$φ$，使得$K（a，b）=φ（a）^T·φ（b）$。 那么你就可以使用K作为内核，因为你知道 $φ$ 存在，即使你不知道 $φ$ 是什么。在高斯RBF内核的情况下，可以看出，$φ$ 实际上将每个训练实例映射到一个无限维空间，所以你不需要实际执行映射是一件好事！请注意，一些经常使用的内核（例如Sigmoid内核）不符合Mercer的所有条件，但它们通常在实践中运行良好。

还有一个未了结的问题我们需要说明。公式5-7显示了用线性SVM分类器如何从对偶解走到原始解，但是如果你应用了核技巧，最终得到的是包含$φ(x^{(i)})$的方程。而$\hat{ w}$的维度数量必须与$φ(x^{(i)})$相同，后者很有可能是巨大甚至无穷大的，你根本没有办法计算。可是不知道$\hat{ w}$该如何做出预测呢？你可以将公式5-7中$\hat{ w}$的公式插入新实例$ x^{(n)}$的决策函数中，这样就得到了一个只包含输入向量之间点积的公式。这时你就可以再次运用核技巧了（见公式5-11）

$\begin{aligned} h_{\widehat{\mathbf{w}}, \hat{b}}\left(\phi\left(\mathbf{x}^{(n)}\right)\right)=& \widehat{\mathbf{w}}^{T} \phi\left(\mathbf{x}^{(n)}\right)+\hat{b}=\left(\sum_{i=1}^{m} \hat{\alpha}^{(i)} t^{(i)} \phi\left(\mathbf{x}^{(i)}\right)\right)^{T} \phi\left(\mathbf{x}^{(n)}\right)+\hat{b} \\=& \sum_{i=1}^{m} \hat{\alpha}^{(i)} t^{(i)}\left(\phi\left(\mathbf{x}^{(i)}\right)^{T} \phi\left(\mathbf{x}^{(n)}\right)\right)+\hat{b} \\=& \sum_{i=1}^{m} \hat{\alpha}^{(i)} t^{(i)} K\left(\mathbf{x}^{(i)}, \mathbf{x}^{(n)}\right)+\hat{b} \\ & \hat{\alpha}^{(i)}>0 \end{aligned}$ 公式5-11

注意，因为$α(i)≠0$仅用于支持向量，涉及计算只有支持向量的新输入向量x(n)的点积，进而进行预测，而不是所有训练实例。 当然，您还需要使用相同的技巧计算偏差项b（公式5-12）。

image-20200731164111698 公式5-12

在线SVM

在结束本章之前，让我们快速浏览一下在线支持向量机分类器。对于线性SVM分类器，一种方法是使用梯度下降(如SGDClassifier)来最小化公式5-13中的代价函数，该代价函数是由原始问题推导出来的。不幸的是，它的收敛速度比基于QP的方法慢得多。

$J(\mathbf{w}, b)=\frac{1}{2} \mathbf{w}^{T} \mathbf{w} \quad+\quad C \sum_{i=1}^{m} \max \left(0,1-t^{(i)}\left(\mathbf{w}^{T} \mathbf{x}^{(i)}+b\right)\right)$ 公式 5-13

成本函数中的第一个会促进模型得到一个较小的权重向量w，从而使得间隔更大。第二项则计算全部的间隔违例。如果没有一个实例位于间隔之中且全部分类正确，那么它的边界违例就等于0。否则，实例的违例数量与其到间隔正确一遍的距离成正比。故将这一项最小化可以确保模型使间隔违例尽可能地小和少。

Hinge损失函数

Extra material

Training time

Linear SVM classifier implementation using Batch Gradient Descent